package com.datastructure.sort;

import java.util.Arrays;

/*
耗时间
 */
public class RadixSort {

    public static void main(String[] args) {
        int arr[] = { 53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    public static void radixSort(int [] arr){

        //得到数组中的最大值
        int max = arr[0]; // 假设第一数就是最大数
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > max){
               max = arr[i];
            }
        }
        // 得到最大数是几位数
        int maxLength = (max + "").length();
        for(int g=0, n = 1;g < maxLength;g++, n *= 10){
            // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
            int [][] bucket = new int[10][arr.length];
            // 我们定义一个一维数组来记录各个桶每次放入数据的个数
            int [] bucketElementCounts = new int[10];

            // 第一轮（针对每个元素的个位进行排序处理）
            for(int j = 0; j < arr.length;j++){
                // 取出每个元素的个位的值
                int digitOfElement = arr[j] /n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
            int index = 0;
            // 遍历每一个桶，并将桶中的数据，放入到原数组
            for(int k = 0; k < bucketElementCounts.length; k++){
                // 如果是桶中，有数据，我们才放入到原数组
                if(bucketElementCounts[k]!=0){
                    // 循环该桶即第k个桶（即第K个一维数组），放入
                    for(int l = 0; l < bucketElementCounts[k];l++){
                        // 取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 第一轮处理后，需要将每个bucketElementCount[k] = 0!!!!!
                bucketElementCounts[k] = 0;
            }
        }
        System.out.println("最终的排序结果为 arr ="+ Arrays.toString(arr));
        // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
//        int [][] bucket = new int[10][arr.length];
//        // 我们定义一个一维数组来记录各个桶每次放入数据的个数
//        int [] bucketElementCounts = new int[10];
//
//        // 第一轮（针对每个元素的个位进行排序处理）
//        for(int j = 0; j < arr.length;j++){
//            // 取出每个元素的个位的值
//            int digitOfElement = arr[j] % 10;
//            // 放入到对应的桶中
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
//            bucketElementCounts[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
//        int index = 0;
//        // 遍历每一个桶，并将桶中的数据，放入到原数组
//        for(int k = 0; k < bucketElementCounts.length; k++){
//            // 如果是桶中，有数据，我们才放入到原数组
//            if(bucketElementCounts[k]!=0){
//                // 循环该桶即第k个桶（即第K个一维数组），放入
//                for(int l = 0; l < bucketElementCounts[k];l++){
//                    // 取出元素放入到arr
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 第一轮处理后，需要将每个bucketElementCount[k] = 0!!!!!
//            bucketElementCounts[k] = 0;
//        }
//
//        // 第二轮（针对每个元素的十位进行排序处理）
//        for(int j = 0; j < arr.length;j++){
//            // 取出每个元素的个位的值
//            int digitOfElement = arr[j] / 10 % 10;
//            // 放入到对应的桶中
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
//            bucketElementCounts[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
//        index = 0;
//        // 遍历每一个桶，并将桶中的数据，放入到原数组
//        for(int k = 0; k < bucketElementCounts.length; k++){
//            // 如果是桶中，有数据，我们才放入到原数组
//            if(bucketElementCounts[k]!=0){
//                // 循环该桶即第k个桶（即第K个一维数组），放入
//                for(int l = 0; l < bucketElementCounts[k];l++){
//                    // 取出元素放入到arr
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 第一轮处理后，需要将每个bucketElementCount[k] = 0!!!!!
//            bucketElementCounts[k] = 0;
//        }
//
//        // 第三轮（针对每个元素的百位进行排序处理）
//        for(int j = 0; j < arr.length;j++){
//            // 取出每个元素的个位的值
//            int digitOfElement = arr[j] / 100 % 10;
//            // 放入到对应的桶中
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
//            bucketElementCounts[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
//        index = 0;
//        // 遍历每一个桶，并将桶中的数据，放入到原数组
//        for(int k = 0; k < bucketElementCounts.length; k++){
//            // 如果是桶中，有数据，我们才放入到原数组
//            if(bucketElementCounts[k]!=0){
//                // 循环该桶即第k个桶（即第K个一维数组），放入
//                for(int l = 0; l < bucketElementCounts[k];l++){
//                    // 取出元素放入到arr
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 第一轮处理后，需要将每个bucketElementCount[k] = 0!!!!!
//            bucketElementCounts[k] = 0;
//        }
//        System.out.println("最终的排序结果为 arr ="+ Arrays.toString(arr));
    }
}
